#include <atomic>
#include <memory>
#include <thread>
#include <iostream>
#include <vector>
#include <cassert>
#include <chrono>

template<typename T>
class SinglePopPush {
private:
    struct node {
        std::shared_ptr<T> data;
        node* next;
        node() : next(nullptr) {}
    };

    std::atomic<node*> head;
    std::atomic<node*> tail;

    node* pop_head() {
        node* const old_head = head.load();
        if (old_head == tail.load()) {
            return nullptr;
        }
        head.store(old_head->next);
        return old_head;
    }

public:
    SinglePopPush() : head(new node), tail(head.load()) {}

    SinglePopPush(const SinglePopPush& other) = delete;
    SinglePopPush& operator=(const SinglePopPush& other) = delete;

    ~SinglePopPush() {
        while (node* const old_head = head.load()) {
            head.store(old_head->next);
            delete old_head;
        }
    }

    std::shared_ptr<T> pop() {
        node* old_head = pop_head();
        if (!old_head) {
            return std::shared_ptr<T>();
        }
        std::shared_ptr<T> const res(old_head->data);
        delete old_head;
        return res;
    }

    void push(T new_value) {
        std::shared_ptr<T> new_data(std::make_shared<T>(new_value));
        node* p = new node;
        p->data = new_data;

        node* const old_tail = tail.load();
        old_tail->data.swap(new_data);   
        old_tail->next = p; 
        tail.store(p);    
    }
};

// Test program
int main() {
    SinglePopPush<int> queue;

    // Producer thread
    std::thread producer([&queue]() {
        for (int i = 0; i < 100; ++i) {
            queue.push(i);
            std::cout << "Produced: " << i << std::endl;
            std::this_thread::sleep_for(std::chrono::milliseconds(10)); // Simulate some work
        }
    });

    // Consumer thread
    std::thread consumer([&queue]() {
        std::vector<std::shared_ptr<int>> consumed;
        int count = 0;
        while (count < 100) {
            std::shared_ptr<int> value = queue.pop();
            if (value) {
                consumed.push_back(value);
                std::cout << "Consumed: " << *value << std::endl;
                count++;
            } else {
                std::this_thread::sleep_for(std::chrono::milliseconds(10)); // Avoid busy waiting
            }
        }

        // Verify that all values were consumed in order
        for (int i = 0; i < 100; ++i) {
            assert(*consumed[i] == i);
        }
    });

    // Wait for both threads to finish
    producer.join();
    consumer.join();

    std::cout << "All tests passed!" << std::endl;
    return 0;
}
